package BFS解决FloodFill算法;

import java.util.LinkedList;
import java.util.Queue;

// 给你一个迷宫数组，然后给你一个随机的位置，让你找到去出口最近的路
// 出口就是矩阵的边缘，然后如果你出生点在边缘的话，这个出生点不能当做出口
// 这个我们可以分布拆解，相当于把每个要走的路线全部列出来，然后找出距离最近的那个
// 通过BFS算法，每次按层序遍历找出最小的出口
public class 离迷宫最近的出口 {
    int [] dx = {0,0,1,-1};
    int [] dy = {1,-1,0,0};

    public int findExit(char[][] maze,int x,int y)
    {
        int m = maze.length;
        int n = maze[0].length;
        boolean[][]visited = new boolean[m][n];

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int []{x,y});
        visited[x][y] = true;
        int step = 0 ;
        while(!q.isEmpty())
        {
            step++;
            int sz = q.size();
            for(int i = 0 ; i < sz ; i++)
            {
                int [] a = q.poll();
                for(int j = 0 ; j < 4 ; j++)
                {
                    int x1 = a[0]+dx[j];
                    int  y1= a[1]+dy[j];
                    if(x1>0 && x1<m && y1>0 && y1<n && !visited[x1][y1] && maze[x1][y1] == '.')
                    {
                        if(x1 == 0 || x1 == m-1 || y1 == 0 || y1 == n-1) return step; //找到出口
                        q.offer(new int[]{x1,y1});
                        visited[x1][y1] = true;
                    }
                }
            }

        }
        return -1;
    }

}
